//
//  5. 最长回文串.swift
//  Top600
//
//  Created by rjb on 2021/8/9.
//

import Foundation
class Solution5 {
    // 最长回文子串
    // 可以用动态规划来做
    // 定义dp[i][j] 以i开头的，以j开头的最长子串
    // 递归表达式 dp[i][j] = dp[i + 1][j -1] + 1   , num[i] == num[j]
    // 定义dp[i][j] 是否是回文子串
    func longestPalindrome(_ s: String) -> String {
        let sArray: [Character] = Array(s)
        
        // 定义dp
        var dp: [[Bool]] = Array(repeating: Array(repeating: false, count: sArray.count + 1), count: sArray.count + 1)
        
        // 对角线都为true
        for i in 0..<sArray.count {
            dp[i][i] = true
        }
        
        // 从整个列表上来看
        // 从i开始到j结束的字符
        var begin = 0
        var maxLength = 1
        // 画出二维表就能知道为什么i是倒着来的
        for i in (0..<sArray.count).reversed() {
            for j in i..<sArray.count {
                let length = j - i + 1
                if sArray[i] == sArray[j] && (length <= 2 || dp[i + 1][j - 1] ) {
                    dp[i][j] = true
                }
                if dp[i][j] && length > maxLength {
                    maxLength = length
                    begin = i
                }
            }
        }
        let start = s.index(s.startIndex, offsetBy: begin)
        let end = s.index(start, offsetBy: maxLength)
        return String(s[start..<end])
    }
    
    static func test() {
        let solution = Solution5()
        let str = "aaaa"
        let result = solution.longestPalindrome(str)
        print(result)
    }
}
